import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {
    //定义一个数组
    public int[] elem;
    public int usedSize;//有效元素个数
    public static final int DEFAULT_SIZE = 10;

    //构造方法
    public TestHeap() {
        elem = new int[DEFAULT_SIZE];//初始化为10个空间
    }

    //给数组赋值的方法
    public void inItElem(int[] array) {
        for (int i = 0; i < elem.length; i++) {
            elem[i] = array[i];//
            usedSize++;//元素个数加1
        }
    }

    /*
     * @ 创建堆的方法
     * */
    public void createHeap(){
        //parent是最后一个子树根节点位置
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            //统一调整方案
            shiftDown(parent, usedSize);
        }
    }

    //向下调整创建大根堆的方法
    /*
     * @param parent 每棵子树的根节点
     * @param len 每棵子树调整的结束位置不能 >len
     * */
    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;//定义子节点的下标
        //保证有左孩子
        while (child < len) {
            //child+1 < len保证有右孩子
            //找左右节点的最大结点
            if(child + 1 < len && elem[child] < elem[child + 1]) {
                //左边小于右边
                child++;//将child指向较大的结点
            }

            //子节点大于父节点
            if (elem[child] > elem[parent]) {
                //交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //由于不能确定调整一次就够了，此时让p指向c
                parent = child;
                child = 2 * parent + 1;
            }else {
                //不大于不需要交换
                break;
            }
        }
    }

    public void offer(int val) {
        //空间满了
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;//元素个数加一个
        shiftUp(usedSize - 1);//
    }

    //向上调整
    public void shiftUp(int childs) {
        int parents = (childs - 1) / 2;
        //childs小于0向上调整结束
        while (childs > 0) {
            //childs大于parents的情况
            if (elem[childs] > elem[parents]) {
                //交换
                int tmp = elem[childs];
                elem[childs] = elem[parents];
                elem[parents] = tmp;
                childs = parents;
                parents = (childs - 1) / 2;
            }else {
                //parents较大
                break;
            }
        }
    }

    //判断是否为满了
    public boolean isFull() {
        return this.usedSize == elem.length;
    }

    /*
    * @ 删除堆顶的元素
    * */
    public int pop() {
        //数组为空
        if (isEmpty()) {
            return -1;//表示数组空间为空
        }
        //不为空
        int tmp = elem[0];//0下标表示的是堆顶元素
        elem[0] = elem[usedSize - 1];//usedSize-1表示的是堆的最后一个元素
        elem[usedSize - 1] = tmp;
        usedSize--;//元素个数减一个
        //调用向下调整来重新让堆变成大根堆
        shiftDown(0, usedSize);
        return tmp;
    }

    //判断是否为空的方法
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //前k个最小值
    public int[] smallesk(int[] arr, int k) {
        //创建最小根
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //将数组中的元素放到堆中
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);//放到堆中
            int usedSize = 0;
        }
        //将弹出的元素放到数组中
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();//弹出
        }
        return tmp;
    }

    //堆中的前k个最大或者最小的数据
    //Top-K问题
    public static int[] smallesks(int[] arr, int k) {
        if (arr == null || k == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //将数组元素放到堆中
        for (int i = 0; i < arr.length ; i++) {
            if (minHeap.size() < k) {
                //直接
                minHeap.offer(arr[i]);
            }else {
                //当前数组元素时arr[i]
                int val = minHeap.peek();//得到此时的堆顶元素
                if (val > arr[i]) {
                    //此时i下标的元素小于堆顶元素 - 出堆顶元素
                    minHeap.poll();//弹出较大的堆顶元素
                    minHeap.offer(arr[i]);//插入现在较小的i小标的数据
                }
            }
        }
        //循环结束 - n-k个元素遍历完成
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();//弹出
        }
        return tmp;
    }

    //堆排序
    public void heapSort() {
        //先建立大根堆
        createHeap();
        int end = usedSize - 1;//堆末尾位置下标
        while (end > 0) {
            //交换
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0 ,end);//调用向下调整堆顶与当前最后一个元素
            end--;
        }
    }

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        testHeap.inItElem(array);
        //testHeap.createHeap();
        //测试向上调整
        //testHeap.offer(50);
        //测试删除
        //System.out.println(testHeap.pop());//会输出65
        testHeap.heapSort();
        //System.out.println("超烦豆先森");
        System.out.println("efsdvsdf");
    }
}